class Solution {
public:
    vector<int> inventoryManagement(vector<int>& nums, int k) {
        srand(time(NULL));
        qsort(nums,0,nums.size()-1,k);
        return {nums.begin(),nums.begin()+k};
    }
    void qsort(vector<int>& nums,int begin,int end,int k)
    {
        if(begin>=end)return;
        int key=getRom(nums,begin,end);
        int i=begin,left=begin-1,right=end+1;
        while(i<right)
        {
            if(nums[i]<key)swap(nums[++left],nums[i++]);
            else if(nums[i]==key)i++;
            else swap(nums[--right],nums[i]);
        }
        int a=left-begin+1,b=right-left-1;
        if(a>=k)qsort(nums,begin,left,k);
        else if(a+b>=k)return;
        else qsort(nums,right,end,k-a-b);
    }
    int getRom(vector<int>& nums,int begin,int end)
    {
        int r=rand();
        return nums[r%(end-begin+1)+begin];
    }
};
